//
// Created by LiuYou on 2021/12/6.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


namespace sort {
    class Sort {
    public:
        static int random(int left, int right) {
            std::random_device randomDevice;
            std::default_random_engine randomEngine( randomDevice());
            std::uniform_int_distribution<> uniformIntDistribution( left, right );
            return uniformIntDistribution( randomEngine );
        }

    public:
        // 堆排序...
        static void heapSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            int heapSize = arr.size();

            // 构建成一个大顶堆。
            for (int i = arr.size() - 1; i >= 0; --i) {
                heapify( arr, i, heapSize );
            }

            while (heapSize > 0) {
                std::swap( arr[0], arr[--heapSize] );
                heapify( arr, 0, heapSize );
            }

        }

        static void heapify(std::vector<int>& arr, int idx, int heapSize) {
            int leftChildIdx = 2 * idx + 1;
            while (leftChildIdx < heapSize) {
                int greatestIdx = leftChildIdx;
                if ((leftChildIdx + 1) < heapSize && arr[leftChildIdx + 1] > arr[leftChildIdx]) {
                    greatestIdx = leftChildIdx + 1;
                }
                if (arr[greatestIdx] > arr[idx]) {
                    std::swap( arr[greatestIdx], arr[idx] );
                    idx = greatestIdx;
                    leftChildIdx = 2 * idx + 1;
                } else {
                    break;
                }
            }
        }

        // ...堆排序

    };

}


using namespace sort;


int main(int argc, char** argv) {

    std::cout << "====================[ 堆排序 ]====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::heapSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }


    return 0;
}
